import sys
input = sys.stdin.readline
inf = float('inf')
def getInt():
return int(input())
def getStr():
return input().strip()
def getList(split=True):
s = getStr()
if split:
s = s.split()
return map(int, s)
t = getInt()
N = 20
def solve():
from math import gcd, log2
from functools import reduce
n = getInt()
a = list(getList())
t = [[0] * N for _ in range(n)]
target = reduce(gcd, a)
for i, j in enumerate(a):
t[i][0] = j
for k in range(1, N):
for i in range(n):
t[i][k] = gcd(t[i][k-1], t[(i + (1 << k-1)) % n][k-1])
def get(l, r):
k = int(log2(r-l+1))
return gcd(t[l][k], t[(r-(1 << k)+1) % n][k])
res = 0
j = 0
for i in range(n):
j = max(j, i)
g = get(i, j)
while g != target:
j += 1
g = gcd(g, a[j % n])
res = max(res, j-i)
print(res)
for _ in range(t):
solve()
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 2e5;
const int LOG_MAX = 19;
const int UNIT = 1, NONE = -1;
int gcdOf (int a, int b) {
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return a;
}
int input[1 + 2 * NMAX]; int n;
int Table[1 + 2 * NMAX][1 + LOG_MAX]; int logOf[1 + 2 * NMAX];
void getTable (int n) {
logOf[1] = 0;
for (int i = 2; i <= 2 * n; i ++)
logOf[i] = logOf[i / 2] + 1;
for (int i = 1; i <= 2 * n; i ++)
Table[i][0] = input[i];
for (int bit = 1; (1 << bit) <= 2 * n; bit ++)
for (int i = 1; i + (1 << bit) - 1 <= 2 * n; i ++)
Table[i][bit] = gcdOf (Table[i][bit - 1], Table[i + (1 << (bit - 1))][bit - 1]);
}
int queryGCD (int i, int j) {
int lg = logOf[j - i + 1];
return gcdOf (Table[i][lg], Table[j - (1 << lg) + 1][lg]);
}
int main()
{
int t; cin >> t;
for (int tc = 1; tc <= t; tc ++) {
cin >> n;
for (int i = 1; i <= n; i ++)
cin >> input[i];
for (int i = n + 1; i <= 2 * n; i ++)
input[i] = input[i - n];
int totalGCD = 0;
for (int i = 1; i <= 2 * n; i ++)
totalGCD = gcdOf (totalGCD, input[i]);
for (int i = 1; i <= 2 * n; i ++)
input[i] /= totalGCD;
getTable (n);
int answer = 0;
for (int i = 1; i <= n; i ++) {
int left = 0, right = n, target = NONE;
while (left <= right) {
int mid = left + (right - left) / 2;
if (queryGCD (i, i + mid) == UNIT) {
target = mid;
right = mid - 1;
}
else
left = mid + 1;
}
answer = max (answer, target);
}
cout << answer << "\n";
}
return 0;
}
1354B - Ternary String | 122B - Lucky Substring |
266B - Queue at the School | 1490A - Dense Array |
1650B - DIV + MOD | 1549B - Gregor and the Pawn Game |
553A - Kyoya and Colored Balls | 1364A - XXXXX |
1499B - Binary Removals | 1569C - Jury Meeting |
108A - Palindromic Times | 46A - Ball Game |
114A - Cifera | 776A - A Serial Killer |
25B - Phone numbers | 1633C - Kill the Monster |
1611A - Make Even | 1030B - Vasya and Cornfield |
1631A - Min Max Swap | 1296B - Food Buying |
133A - HQ9+ | 1650D - Twist the Permutation |
1209A - Paint the Numbers | 1234A - Equalize Prices Again |
1613A - Long Comparison | 1624B - Make AP |
660B - Seating On Bus | 405A - Gravity Flip |
499B - Lecture | 709A - Juicer |